package leetcode.recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//39. 组合总和
//40. 组合总和 II
public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (candidates.length == 0) {
            return res;
        }
        backtrace(res, path, candidates, target, 0, candidates.length);
        return res;
    }

    private void backtrace(List<List<Integer>> res, List<Integer> path,
                           int[] candidates, int target, int start, int length) {

        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < length; i++) {
            path.add(candidates[i]);
            backtrace(res, path, candidates, target - candidates[i], i, length);
            path.remove(path.size() - 1);
        }
    }


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (candidates.length == 0) {
            return res;
        }
        Arrays.sort(candidates);
        backtrace2(res, path, candidates, target, 0, candidates.length);
        return res;
    }

    private void backtrace2(List<List<Integer>> res, List<Integer> path,
                            int[] candidates, int target, int start, int length) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            if (i > start && candidates[i - 1] == candidates[i]) {
                continue;
            }
            path.add(candidates[i]);
            backtrace(res, path, candidates, target - candidates[i], i + 1, length);
            path.remove(path.size() - 1);
        }
    }


    // 二战
    public List<List<Integer>> combinationSumP1(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int n = candidates.length;
        // 由于可以重复使用元素，所以不需要used数组
        backtracing(candidates, target, 0, res, path, n);
        return res;
    }

    private void backtracing(int[] candidates, int target,
                             int start, List<List<Integer>> res,
                             List<Integer> path, int n) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < n; i++) {
            path.add(candidates[i]);
            backtracing(candidates, target - candidates[i],
                    i, res, path, n);
            // 回溯
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> combinationSumP2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int n = candidates.length;

        // 由于数组中的元素只能使用一次，所以需要定义used数组来判断
        boolean[] used = new boolean[n];
        Arrays.sort(candidates);
        backtracing2(candidates, target, 0, res, path, n, used);

        return res;
    }

    private void backtracing2(int[] candidates, int target,
                              int start, List<List<Integer>> res,
                              List<Integer> path, int n,
                              boolean[] used) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
        }
        for (int i = start; i < n; i++) {

            if (used[i] || (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(candidates[i]);
            backtracing2(candidates,
                    target - candidates[i], i, res, path, n, used);
            // 回溯
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
